public class Solution307 {

    int[] h;
    int n;
    int[] nums;

    private void up(int x,int d){
        while (x<=n){
            h[x]+=d;
            x+=lowbot(x);
        }
    }

    private int lowbot(int x) {
        return x&(-x);
    }

    public Solution307(int[] nums) {
        n=nums.length;
        this.nums=nums;
        h=new int[n+1];
        for (int i=0;i<nums.length;i++){
            up(i+1,nums[i]);
        }
    }

    public void update(int index, int val) {
        int sub=-nums[index]+val;
        nums[index]=val;
        up(index+1,sub);
    }

    public int sumRange(int left, int right) {
        int a=query(left);
        int b=query(right+1);
        return b-a;
    }

    private int query(int x) {
        int t=0;
        while (x>0){
            t+=h[x];
            x-=lowbot(x);
        }
        return t;
    }

    public static void main(String[] args) {
        Solution307 solution307=new Solution307(new int[]{1,3,5});
        System.out.println(solution307.sumRange(0, 2));
        solution307.update(1,2);
        System.out.println(solution307.sumRange(0, 2));
    }
}
